package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/7/27.<br><br>
 *
 * 从中序与后序遍历序列构造二叉树
 */
public class Topic106 {

    public static void main(String[] args) {
        Topic106 instance = new Topic106();

        int[] inorder = new int[] {9,3,15,20,7};
        int[] postorder = new int[] {9,15,7,20,3};

        TreeNode root = instance.buildTree(inorder, postorder);
        Util.preTravelTree(root);
        System.out.println();

        Util.inTravelTree(root);
        System.out.println();

        Util.postTravelTree(root);
        System.out.println();
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(postorder.length - 1, 0, inorder.length - 1, inorder, postorder);
    }

    private TreeNode helper(int postEnd, int inStart, int inEnd, int[] inorder, int[] postorder) {
        if(postEnd < 0 || inStart > inEnd) {
            return null;
        }

        TreeNode node = new TreeNode(postorder[postEnd]);
        int index = 0;
        for(int i = inStart; i <= inEnd; i++) {
            if(node.val == inorder[i]) {
                index = i;
                break;
            }
        }

        node.left = helper(postEnd -  (inEnd - index) - 1, inStart, index - 1, inorder, postorder);
        node.right = helper(postEnd - 1, index + 1, inEnd, inorder, postorder);
        return node;
    }
}
